# -*- coding: utf-8 -*-
"""
# @Time    : 2017/12/21 17:59
# @Author  : wangqunsong
# @Email   : wangqunsong@hotmail.com
# @File    : dichotomy.py
# @Software: PyCharm
"""


def binarySearch(list,item):
    '''
    用于在给定的list中查询指定元素item，并返回item在list中的位置，若item不存在，则返回none
    算法复杂度为O(log2n)
    '''
    low = 0
    high = len(list) - 1   #low和high用于跟踪要在其中查找的列表部分

    while low <= high:
        mid = (int)((low + high) / 2)
        guess = list[mid]

        if item == guess:             #找到了item
            return mid
        elif guess > item:           #猜的数字过大
            high = mid - 1
        else:                        #猜的数字过小
            low = mid + 1
    return  None

def main():
    testList = [1,2,3,4,5,6,7,8,9]
    print(binarySearch(testList,7))
    print(binarySearch(testList,-1))

if __name__ == '__main__':
    main()

